// =====================================================================================
//
//       Filename:  heap.cpp
//
//    Description:  Implémentation d'une structure de tas, où l'élément minimal occupe la
//					racine
//
//        Version:  1.0
//        Created:  18/08/2009 09:40:00
//       Revision:  none
//       Compiler:  g++
//
//         Author:  François Hissel (fh), francois.hissel@m4x.org
//        Company:
//
// =====================================================================================

#include	"heap.h"

/************************************/
/* IMPLEMENTATION DE LA CLASSE HEAP */
/************************************/
template<class T,typename Compare>
Heap<T,Compare>::Heap():root(0),_size(0) {
	if (sizeof(T)>sizeof(HeapNode<T,Compare>*)*3+sizeof(_size)) _exchange_method=false; else _exchange_method=true;
}

template<class T,typename Compare>
void Heap<T,Compare>::insert(const T &element) {
	if (root==0) {
		root=new HeapNode<T,Compare>(element,0,0,0,0);
		_size=1;
		return;
	}
	//On descend jusqu'au parent de la première feuille libre dans le tas
	_size++;
	HeapNode<T,Compare> *hn=seek(_size/2);
	//On insère l'élément à l'emplacement libre
	HeapNode<T,Compare> *hn2=new HeapNode<T,Compare>(element,0,0,hn,0);
	hn->children[_size%2]=hn2;
	//On fait remonter la bulle jusqu'à ce qu'on rencontre un élément inférieur ou la racine du tas
	move_up(hn2);
}

template<class T,typename Compare>
T &Heap<T,Compare>::peek() const {
	if (root==0) throw "No element";
	return root->data;
}

template<class T,typename Compare>
T Heap<T,Compare>::pop() {
	if (root==0) throw "No element";
	T res=root->data;
	//Si l'arbre ne contient qu'un noeud, on le supprime
	if (_size==1) {
		_size=0;
		delete root;
		root=0;
		return res;
	}
	//On échange la racine avec le dernier noeud
	HeapNode<T,Compare> *hn=seek(_size);
	root->data=hn->data;
	hn->parent->children[_size%2]=0;
	delete hn;
	_size--;
	//On fait descendre la racine jusqu'à ce qu'elle soit inférieure à ses enfants
	move_down(root);
	return res;
}

template<class T,typename Compare>
void Heap<T,Compare>::set_data(HeapNode<T,Compare> *node,const T &newdata) {
	bool higher=_compare(node->data,newdata);
	node->data=newdata;
	if (higher) {	//Si la nouvelle valeur est supérieure, il faut descendre le noeud
		move_down(node);
	} else {	//Sinon, on fait remonter le noeud dans l'arbre
		move_up(node);
	}
}

template<class T,typename Compare>
void Heap<T,Compare>::adjust(HeapNode<T,Compare> *node) {
	if (node->parent!=0 && _compare(node->data,node->parent->data)) move_up(node);
	else if (node->children[0]!=0 && _compare(node->children[0]->data,node->data)) move_down(node);
	else if (node->children[1]!=0 && _compare(node->children[1]->data,node->data)) move_down(node);
}

template<class T,typename Compare>
void Heap<T,Compare>::move_down(HeapNode<T,Compare> *node) {
	while (node!=0) {
		if (node->children[1]!=0 && _compare(node->children[1]->data,node->children[0]->data) && _compare(node->children[1]->data,node->data)) {
			exchange_with_child(node,1);
			node=node->children[1];
		}
		else if (node->children[0]!=0 && _compare(node->children[0]->data,node->data)) {
			exchange_with_child(node,0);
			node=node->children[0];
		}
		else node=0;
	}
}

template<class T,typename Compare>
void Heap<T,Compare>::move_up(HeapNode<T,Compare> *node) {
	while (node->parent!=0 && _compare(node->data,node->parent->data)) {
		//Si le parent est supérieur, on échange l'élément avec son parent
		int num=0;
		if (node->parent->children[0]==node) num=0; else num=1;
		node=node->parent;
		exchange_with_child(node,num);
	}
}

template<class T,typename Compare>
HeapNode<T,Compare> *Heap<T,Compare>::seek(unsigned int num) const {
	if (num>_size) return 0;
	unsigned int s=1;
	while (s<=num) s*=2;
	s/=2;
	unsigned int s2=num-s;
	HeapNode<T,Compare> *hn=root;
	while (s>1) {
		s/=2;
		hn=hn->children[s2/s];
		s2&=(~s);
	}
	return hn;
}

template<class T,typename Compare>
void Heap<T,Compare>::exchange_with_child(HeapNode<T,Compare> *&source,unsigned short child) {
	if (child>=2 || source==0 || source->children[child]==0) return;
	if (_exchange_method) {
		T tmp=source->data;
		source->data=source->children[child]->data;
		source->children[child]->data=tmp;
	} else {
		HeapNode<T,Compare> *sav[2];
		HeapNode<T,Compare> *sc=source->children[child];
		for (int i=0;i<2;++i) sav[i]=sc->children[i];
		sc->children[child]=source;
		sc->children[1-child]=source->children[1-child];
		sc->parent=source->parent;
		if (source==root) {
			root=sc;
		} else {
			for (int i=0;i<2;++i) if (source->parent->children[i]==source) source->parent->children[i]=sc;
		}
		int tmp=source->_depth;
		source->_depth=sc->_depth;
		sc->_depth=tmp;
		source->parent=sc;
		for (int i=0;i<2;++i) source->children[i]=sav[i];
		source=sc;
	}
}

template<class T,typename Compare>
void Heap<T,Compare>::display(ostream &out) {
	if (root) root->display(out,0);
}

/****************************************/
/* IMPLEMENTATION DE LA CLASSE HEAPNODE */
/****************************************/
template<class T,typename Compare>
int HeapNode<T,Compare>::depth() {
	if (_depth<0) {
		int dc[2];
		for (int i=0;i<2;++i) dc[i]=(children[i])?children[i]->depth()+1:0;
		if (dc[0]>dc[1]) _depth=dc[0]; else _depth=dc[1];
	}
	return _depth;
}

template<class T,typename Compare>
HeapNode<T,Compare>::~HeapNode() {
	for (int i=0;i<2;++i) delete children[i];
}

template<class T,typename Compare>
HeapNode<T,Compare> *HeapNode<T,Compare>::find(const T &source) {
	if (_compare(source,data)) return 0;
	if (data==source) return this;
	HeapNode<T,Compare> *hn=0;
	if (children[0]) hn=children[0]->find(source);
	if (hn!=0) return hn;
	if (children[1]) hn=children[1]->find(source);
	return hn;
}

template<class T,typename Compare>
void HeapNode<T,Compare>::display(ostream &out,int border) {
	for (int i=0;i<border;++i) out << "\t";
	out << data << "\n";
	for (int i=0;i<2;++i) if (children[i]) children[i]->display(out,border+1);
}

